package com.it.alg;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.function.Consumer;

import com.it.io.IOSequence;

public class Stack<S, E> implements Iterable<E> {

	class Node {
		E value;
		int repeatCount = 1;
		Node prev;
		Node next;
	}
	
	final Node head;
	final Node tail;
	Node top;
	int size;
	int modCount = 0;
	
	IOSequence<S, E> ioSequence;
	
	public Stack() {
		this.head = new Node();
		this.tail = new Node();
		this.head.next = this.tail;
		this.tail.prev = this.head;
		this.top = head;
	}
	
	public NodeInfo<E> push(E value) {
		modCount++;
		Node node = new Node();
		node.value = value;
		node.prev = top;
		node.next = top.next;
		top.next.prev = node;
		top.next = node;
		top = node;
		size++;
		setCount(top);
		return new NodeInfo<E>(top.value, top.repeatCount);
	}
	
	public NodeInfo<E> push() {
		if (top.next == tail) {
			throw new NoSuchElementException();
		}
		modCount++;
		top = top.next;
		setCount(top);
		return new NodeInfo<E>(top.value, top.repeatCount);
	}
	
	public NodeInfo<E> pop() {
		return remove(top);
	}
	
	public NodeInfo<E> add(E value) {
		modCount++;
		Node node = new Node();
		node.value = value;
		node.repeatCount = 1;
		node.prev = tail.prev;
		node.next = tail;
		tail.prev.next = node;
		tail.prev = node;
		size++;
		return new NodeInfo<E>(node.value, node.repeatCount);
	}
	
	public NodeInfo<E> remove(Node node) {
		if (node == head || node == tail) {
			throw new NoSuchElementException();
		}
		modCount++;
		Node prev = node.prev;
		Node next = node.next;
		prev.next = next;
		next.prev = prev;
		node.prev = null;
		node.next = null;
		if (top == node) {
			top = prev;
		}
		size--;
		return new NodeInfo<E>(node.value, node.repeatCount);
	}
	
	public int size() {
		return size;
	}
	
	public boolean isAllPushed() {
		return top.next == tail;
	}

	public String nodesToString(String separator) {
		StringBuilder buf = new StringBuilder(size);
		for (E value : this) {
			buf.append(value).append(separator);
		}
		return buf.substring(0, buf.length() - separator.length());
	}
	
	@Override
	public String toString() {
		return this.nodesToString(" ");
	}
	
	private void setCount(Node node) {
		Node prev = node.prev;
		if (prev == head) {
			node.repeatCount = 1;
		} else {
			if (prev.value == node.value
					|| node.value != null
					&& node.value.equals(prev.value)) {
				node.repeatCount = prev.repeatCount + 1;
			} else {
				node.repeatCount = 1;
			}
		}
	}
	
	@Override
	public Iterator<E> iterator() {
		return new Itr();
	}
	
	private class Itr implements Iterator<E> {
        Node cursor = head.next;
        int expectedModCount = modCount;

        Itr() {}

        public boolean hasNext() {
            return cursor != tail;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
            E value = cursor.value;
            cursor = cursor.next;
            return value;
        }

        public void remove() {
            checkForComodification();
            Stack.this.remove(cursor);
            expectedModCount = modCount;
        }

        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            checkForComodification();
            for (; cursor != tail && modCount == expectedModCount; cursor = cursor.next) {
            	E value = cursor.value;
            	action.accept(value);
            }
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

}